package pacBioSimple;

public class NeedlemanWunsch {
	
	/**
	 * a simple quic NeedlemanWunsch algo
	 */
	private int[][] E;
	private int[][] I;
	private String n,m;
	private int g=0;
	private int e=0;
	public NeedlemanWunsch(String a, String b,int d)
	{
		n=a;
		m=b;
		E = new int[n.length()+1][m.length()+1];
		this.g=d;
		init();
	}
	
	public NeedlemanWunsch(String a, String b, int g, int e)
	{
		n=a;
		m=b;
		E = new int[n.length()+1][m.length()+1];
		I = new int[n.length()+1][m.length()+1];
		this.g=g;
		this.e=e;
		init_gap_matrix();
	}
	
	public NeedlemanWunsch(AlignmentObject tobeAlign)
	{
		n=tobeAlign.getA();
		m=tobeAlign.getTemplate();
		E = new int[n.length()+1][m.length()+1];
		I = new int[n.length()+1][m.length()+1];
		this.g=tobeAlign.getGap();
		this.e=tobeAlign.getEx();
		init_gap_matrix();
	}
	
	
	private void init_gap_matrix()
	{
		I[0][0]=Integer.MIN_VALUE;
		for(int i=1; i<=n.length();++i)
		{
			E[i][0]=-g-(i-1)*e;
			I[i][0]=-g-(i-1)*e;
		}
		for(int i=1; i<=m.length();++i)
		{
			E[0][i]=-g-(i-1)*e;
			I[0][i]=-g-(i-1)*e;
		}
		
	}
	private  void init()
	{
		E[0][0]=0;
		for(int i=1; i <=n.length();++i)
		{
			E[i][0]=0;
		}
		for(int j=1;j<=m.length();++j)
		{
			E[0][j]=0;
		}
	}
	
	private int cost(char a, char b)
	{
		if(a==b) return 2;
		else return -1;
	}
	
	
	//simple quadradic space algo todo k-banded and linar space
	public int compare()
	{
		for(int i=1; i<=n.length();++i)
		{
			for(int j=1; j<=m.length();++j)
			{
				E[i][j]=Math.max(E[i-1][j-1]+cost(n.charAt(i-1),m.charAt(j-1)),Math.max(E[i-1][j]-g,E[i][j-1]-g));
			}
		}
		return E[n.length()][m.length()];
	}
	
	public double affineCompare()
	{
		
		for(int i=1; i<=n.length();++i)
		{
			for(int j=1; j<=m.length();++j)
			{
				int score = cost(n.charAt(i-1),m.charAt(j-1));
				E[i][j]=Math.max(E[i-1][j-1]+score,I[i-1][j-1]+score);
				I[i][j]=Math.max(E[i-1][j]-g,Math.max(I[i-1][j]-e,Math.max(E[i][j-1]-g,I[i][j-1]-e)));
			}
		}
		double max = Math.max(n.length(),m.length());
		return (E[n.length()][m.length()])/max;
	}
	
	public AlignmentObject affineCompareWithTraceBack()
	{
		int[][] T = new int[n.length()+1][m.length()+1];
		T[0][0]=0;
		for(int i=1; i < n.length();++i)
		{
			T[i][0]=2;
		}
		for(int j=1;j < m.length();++j)
		{
			T[0][j]=3;
		}
		
		for(int i=1; i<=n.length();++i)
		{
			for(int j=1; j<=m.length();++j)
			{
				int score = cost(n.charAt(i-1),m.charAt(j-1));
				int iVal=I[i-1][j-1];
				if(i==1 && j==1 && score <0)
				{
					iVal=I[i-1][j-1];
				}
				else
				{
					iVal=I[i-1][j-1]+score;
				}
				E[i][j]=Math.max(E[i-1][j-1]+score,iVal);
//				int k=E[i-1][j]-g;
//				int l=I[i-1][j]-e;
//				int t=E[i][j-1]-g;
//				int y=I[i][j-1]-e;
				I[i][j]=Math.max(E[i-1][j]-g,Math.max(I[i-1][j]-e,Math.max(E[i][j-1]-g,I[i][j-1]-e)));
				
				if(E[i][j]>=I[i][j])
				{
					T[i][j]=1;
				}
				else
				{
					if(Math.max(E[i-1][j]-g, I[i-1][j]-e)>Math.max(E[i][j-1]-g, I[i][j-1]-e))
					{
						T[i][j]=2;
					}
					else
					{
						T[i][j]=3;
					}
				}
			}
		}
		AlignmentObject aligned = new AlignmentObject();
		
		double max = Math.max(n.length(),m.length());
		aligned.setScore(E[n.length()][m.length()]/max);
		traceback(T);
		aligned.setTemplate(m);
		aligned.setA(n);

		return aligned;
	}
	
	private void traceback(int[][]T)
	{
		int i=n.length();
		int j=m.length();
		StringBuilder a= new StringBuilder();
		StringBuilder b= new StringBuilder();
		while(T[i][j]!=0)
		{
			if(T[i][j]==1)
			{
				a.append(n.charAt(i-1));
				b.append(m.charAt(j-1));
				i=i-1;
				j=j-1;
			}
			else if(T[i][j]==2)
			{
				a.append(n.charAt(i-1));
				b.append('-');
				i=i-1;
			}
			else if(T[i][j]==3)
			{
				a.append('-');
				b.append(m.charAt(j-1));
				j=j-1;
			}
		}
		n=a.reverse().toString();
		m=b.reverse().toString();		
	}

	public String getN() {
		return n;
	}

	public void setN(String n) {
		this.n = n;
	}

	public String getM() {
		return m;
	}

	public void setM(String m) {
		this.m = m;
	}
	
	
	
}
